/*************************************************************************
	> File Name: radix_sort.cpp
	> Author: 
	> Mail: 
	> Created Time: Thu 08 Aug 2024 10:52:59 AM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "0.sort_test.h"
#define K 65536

void radixSort(int *arr, int l, int r) {
	int *cnt = (int *)malloc(sizeof(int) * K);
	int *temp = (int *)malloc(sizeof(int) * (r - l));
	// round 1
	memset(cnt, 0, sizeof(int) * K);
	for(int i = l; i < r; i++) {
		cnt[arr[i] % K]++;
	}
	for(int i = 1; i < K; i++) {
		cnt[i] += cnt[i - 1];
	}
	for(int i = r - 1; i >= l; --i) {
		temp[--cnt[arr[i] % K]] = arr[i];
	}
	memcpy(arr + l, temp, sizeof(int) * (r - l));
	// round 2
	memset(cnt, 0, sizeof(int) * K);
	for(int i = l; i < r; i++) {
		cnt[arr[i] / K]++;
	}
	for(int i = 1; i < K; i++) {
		cnt[i] += cnt[i - 1];
	}
	for(int i = r - 1; i >= l; --i) {
		temp[--cnt[arr[i] / K]] = arr[i];
	}
	memcpy(arr + l, temp, sizeof(int) * (r - l));
	free(cnt);
	free(temp);
}

int main() {
	int *arr_small = getRandData(SMALL_DATA);
	int *arr_big = getRandData(BIG_DATA);
	TEST(radixSort, arr_small, SMALL_DATA);
	printf("\n");
	TEST(radixSort, arr_big, BIG_DATA);
	printf("\n");
	free(arr_small);
	free(arr_big);
	return 0;
}

